#+TITLE: Laziness in Scheme
#+SUBTITLE: How to create lazy constructs in Scheme
#+TAGS: scheme, lazy,
#+AUTHOR: Zelphir Kaltstahl
#+CREATOR: Emacs
#+LANGUAGE: English
#+EXCLUDE_TAGS: noexport, notexported
#+OPTIONS: ^:{} H:10 toc:2

* Laziness using plain lambda expressions

Some prerequisites to make later code more readable:

#+NAME: prerequisites
#+BEGIN_SRC scheme :noweb yes :results output :exports code :eval never-export
(define println
  (lambda* (msg #:optional (output-port (current-output-port)))
    (display (simple-format #f "~a\n" msg) output-port)))
#+END_SRC

We can define lazy lists by making the cdr of a list a lambda expression, which is only applied, when the cdr is needed.

#+NAME: lazy-definition
#+BEGIN_SRC scheme :noweb yes :results output :exports code :eval never-export
(define lazy-list
  (lambda* (start #:optional (end #f))
    (cond
     [end
      (if (<= start end)
          (cons start
                (λ () (lazy-list (+ start 1) end)))
          '())]
     [else
      (cons start
            (λ () (lazy-list (+ start 1))))])))

(define lazy-car car)

(define lazy-cdr
  (λ (lazy-lst)
    ((cdr lazy-lst))))
#+END_SRC

Creating a lazy list works as follows:

#+BEGIN_SRC scheme :noweb yes :results output verbatim drawer replace :exports both :eval never-export
<<lazy-definition>>

(display
 (simple-format
  #f "~a\n"
  (lazy-list 0 10)))
#+END_SRC

#+RESULTS:
:RESULTS:
(0 . #<procedure 7f125bf81b40 at <unknown port>:11:16 ()>)
:END:

Iterating through a lazy list up to a given number:

#+BEGIN_SRC scheme :noweb yes :results output verbatim drawer replace :exports both :eval never-export
<<prerequisites>>
<<lazy-definition>>

(let ([infinite-list (lazy-list 0 +inf.0)])
  (let iter ([counter 0] [llst infinite-list])
    (cond
     [(< counter 10)
      (println (lazy-car llst))
      (iter (+ counter 1) (lazy-cdr llst))]
     [else
      'done])))
#+END_SRC

#+RESULTS:
:RESULTS:
0
1
2
3
4
5
6
7
8
9
:END:

Also higher-order list functions can be defined for lazy lists:

#+NAME: lazy-higher-order-list-functions
#+BEGIN_SRC scheme :noweb yes :results output verbatim drawer replace :exports both :eval never-export
<<lazy-definition>>

(define lazy-filter
  (λ (pred lazy-list)
    (cond
     [(null? lazy-list) '()]
     [(pred (lazy-car lazy-list))
      (cons (lazy-car lazy-list)
            (λ () (lazy-filter pred (lazy-cdr lazy-list))))]
     [else
      (lazy-filter pred (lazy-cdr lazy-list))])))

(define lazy-map
  (λ (proc lazy-list)
    (cond
     [(null? lazy-list) '()]
     [else
      (cons (proc (lazy-car lazy-list))
            (λ () (lazy-map proc (lazy-cdr lazy-list))))])))
#+END_SRC

#+RESULTS: lazy-higher-order-list-functions
:RESULTS:
:END:

For usage:

#+BEGIN_SRC scheme :noweb yes :results output verbatim drawer replace :exports both :eval never-export
<<prerequisites>>
<<lazy-definition>>
<<lazy-higher-order-list-functions>>

(println "some even numbers:")

(let ([infinite-list
       (lazy-filter (λ (num) (= (remainder num 2) 0))
                    (lazy-list 0 +inf.0))])
  (let iter ([counter 0] [llst infinite-list])
    (cond
     [(< counter 10)
      (println (lazy-car llst))
      (iter (+ counter 1) (lazy-cdr llst))]
     [else
      'done])))

(println "some odd numbers squared:")

(let ([infinite-list
       (lazy-map (λ (num) (* num num))
                 (lazy-filter (λ (num) (= (remainder num 2) 1))
                              (lazy-list 0 +inf.0)))])
  (let iter ([counter 0] [llst infinite-list])
    (cond
     [(< counter 10)
      (println (lazy-car llst))
      (iter (+ counter 1) (lazy-cdr llst))]
     [else
      'done])))
#+END_SRC

#+RESULTS:
:RESULTS:
some even numbers:
0
2
4
6
8
10
12
14
16
18
some odd numbers squared:
1
9
25
49
81
121
169
225
289
361
441
529
625
729
841
961
1089
1225
1369
1521
1681
1849
2025
2209
2401
2601
2809
3025
3249
3481
3721
3969
4225
4489
4761
5041
5329
5625
5929
6241
6561
6889
7225
7569
7921
8281
8649
9025
9409
9801
10201
10609
11025
11449
11881
12321
12769
13225
13689
14161
14641
15129
15625
16129
16641
17161
17689
18225
18769
19321
19881
20449
21025
21609
22201
22801
23409
24025
24649
25281
25921
26569
27225
27889
28561
29241
29929
30625
31329
32041
32761
33489
34225
34969
35721
36481
37249
38025
38809
39601
:END:

* Laziness using macros

It is also possible to write some macro, which takes care of transforming an expression into a lazily evaluated expression.

#+NAME: laziness-using-macros-definition
#+BEGIN_SRC scheme :noweb yes :results output verbatim drawer replace :exports code :eval never-export
;; Macro expansion is at read time, not at run time, so the expression will not
;; be evaluated here.
(define-syntax my-delay
  (syntax-rules ()
    ;; Match the expression that starts is (delay some-expression)
    [(_ expr)
     ;; Wrap that expression in a lambda, which delays evaluation, until the
     ;; resulting expression is applied.
     (lambda () expr)]))

;; The counterpart ~force~ can be defined as a simple procedure, because it does
;; not need to prevent evaluation. It is supposed to cause evaluation. It
;; receives a promise, which in this case is only a lambda expression taking no
;; arguments and applies it.
(define my-force
  (lambda (promise)
    (promise)))
#+END_SRC

#+RESULTS: laziness-using-macros-definition
:RESULTS:
:END:

And here is the usage:

#+NAME: laziness-using-macros-usage
#+BEGIN_SRC scheme :noweb yes :results output verbatim drawer replace :exports both :eval never-export
<<laziness-using-macros-definition>>

(display
 (simple-format
  #f "~a\n"
  (my-delay (+ 5 6))))

(display
 (simple-format
  #f "~a\n"
  (let ((delayed (my-delay (+ 5 6))))
    (my-force delayed))))
#+END_SRC

#+RESULTS: laziness-using-macros-usage
:RESULTS:
#<procedure e5ed50 at <unknown port>:26:2 ()>
11
:END:

* Laziness using SRFI-45

There is also an SRFI, which defines an interface for lazy evaluation.

TODO

* Laziness and streams

Laziness is also connected to implementation of streams. Streams can be of arbitrary length, so it would be a good idea to not have to keep all data of a stream in memory. This is where laziness comes in.

TODO
